Data communication systems comprise three basic components: a transmitter; a transmission channel; and a receiver. Transmitted data become altered due to noise corruption and channel distortion. To reduce the presence of errors caused by noise corruption and channel distortion, redundancy is intentionally introduced, and the receiver uses a decoder to make corrections. In modern data communication systems, the use of error correction codes plays a fundamental role in achieving transmission accuracy, as well as in increasing spectrum efficiency. Using error correction codes, the transmitter encodes the data by adding parity check information and sends the encoded data through the transmission channel to the receiver. The receiver uses the decoder to decode the received data and to make corrections using the added parity check information.
Low Density Parity Check (LDPC) codes were first disclosed by Gallanger in the early 1960's, R. G. Gallager: “Low Density Parity Check Codes”, Cambridge, Mass.: MIT Press, 1963. LDPC codes are linear codes which have been found to be capable of error correcting performance close to the Shannon limit, as disclosed in D. J. C. MacKay and R. M. Neal: “Near Shannon limit performance of low density parity check codes”, Electron. Lett., vol. 32, no. 18, pp. 1645-1646, 1996, and in T. J. Richardson and R. Urbanke: “The capacity of low density parity check codes under message passing decoding”, IEEE Trans. Inform. Theory, vol. 47, pp. 599-618, February 2001. Shortly after the development of Turbo codes researchers noticed that existing graphical representations such as Bayesian networks and factor graphs are unifying frameworks for LDPC decoding using a Sum Product (SP) process involving message passing over the edges of a factor graph, as disclosed in F. Kschischang, B. Frey, and H. Loeliger: “Factor graphs and the sum product algorithm”, IEEE Trans. Inform. Theory, vol. 47, no. 2, pp. 498-519, February 2001. Unfortunately, hardware implementations of LDPC decoders based on this process are highly complex and costly.
Stochastic computation has been introduced in the 1960's as a method to design low precision digital circuits and is described, for example, in B. Gaines: “Advances in Information Systems Science”, Plenum, New York, 1969, ch. 2, pp. 37-172. Stochastic computation has been used, for example, in neural networks. The main feature of stochastic computation is that probabilities are represented as streams of digital bits which are manipulated using simple circuitry. Its simplicity has made it attractive for the implementation of error correcting decoders in which complexity and routing congestion are major problems, as disclosed in the following references:    V. Gaudet and A. Rapley: “Iterative decoding using stochastic computation”, Electron. Lett., vol. 39, no. 3, pp. 299-301, February 2003;    C. Winstead, V. Gaudet, A. Rapley, and C. Schlegel: “Stochastic iterative decoders”, in Proc. of the IEEE Int. Symp. on Information Theory, September 2005, pp. 1116-1120;    C. Winstead: “Error control decoders and probabilistic computation”, in Tohoku Univ. 3rd SOIM-COE Conf., Sendai, Japan, October 2005; and,    W. Gross, V. Gaudet, and A. Milner: “Stochastic implementation of LDPC decoders”, in the 39th Asilomar Conf. on Signals, Systems, and Computers, Pacific Grove, Calif., November 2005.
A major difficulty observed in stochastic decoding is the sensitivity to the level of switching activity—bit transition—for proper decoding operation, i.e. switching events become too rare and a group of nodes become locked into one state. To overcome this “latching” problem, C. Winstead, V. Gaudet, A. Rapley, and C. Schlegel: “Stochastic iterative decoders”, in Proc. of the IEEE Int. Symp. on Information Theory, September 2005, pp. 1116-1120, teach “packetized supernodes” which prevent correlation between messages. A supernode is a special node which tabulates the incoming stochastic messages in histograms, estimates their probabilities and regenerates uncorrelated stochastic messages using random number generators. Unfortunately, the introduction of supernodes diminishes the advantages of the stochastic computation by necessitating complex hardware for implementing the supernodes. In addition to supernodes, C. Winstead: “Error control decoders and probabilistic computation”, in Tohoku Univ. 3rd SOIM-COE Conf., Sendai, Japan, October 2005, teaches scaling of channel LLRs to a maximum value to ensure the same level of switching activity for each block.
Unfortunately, these methods are not capable of successfully decoding state-of-the-art capacity-approaching LDPC codes on factor graphs.
It would be highly desirable to overcome the above limitations of the state of the art and to provide a method for iterative stochastic decoding of state-of-the-art capacity-approaching LDPC codes on factor graphs.